package com.banade.learn.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://blog.csdn.net/qq_32424059/article/details/103107567
 */
public class MaxSumDivThree {

    public int math(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 3 == 0) {
            return sum;
        }
        if (nums.length < 3) {
            if (sum % 3 != 0)
                return 0;
        }

        Arrays.sort(nums);
        List<Integer> two = new ArrayList<>();
        List<Integer> one = new ArrayList();
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 3 == 2) {
                two.add(nums[i]);
            }
            if (nums[i] % 3 == 1) {
                one.add(nums[i]);
            }
        }
        if (sum % 3 == 2) {
            int t1 = 0, t2 = 0;
//            可以删除一个模为 2 的最小数
            if (two.size() >= 1) {
                t2 = two.get(0);
            }
            if (one.size() >= 2) {
                t1 = one.get(0) + one.get(1);
            }

//          选择两种可能中较小的值删除
            if (t1 > t2) {
                return sum - t1;
            } else
                return sum - t2;

        }
        if (sum % 3 == 1) {
            if (two.size() >= 2) {
                if (two.get(0) + two.get(1) > one.get(0)) {
                    result = sum - one.get(0);
                } else
                    result = sum - two.get(0) - two.get(1);
            } else {
                if (one.size() >= 1)
                    result = sum - one.get(0);
                else
                    return 0;
            }
        }
        return result;
    }


//    dfs就是随机选定一个起点将其标记为已经访问过的点，然后就是递归调用进行与其相邻的点的搜索，直到所有的点都被访问完。
//    https://blog.csdn.net/li_jeremy/article/details/83714298
    private int maxSum = 0;

    public int dfs(int[] nums) {
        dfs(nums, 0, 0);
        return maxSum;
    }

    public void dfs(int[] nums, int i, int sum) {
        if (i == nums.length) {
            if (sum % 3 == 0) {
                maxSum = Math.max(maxSum, sum);
            }
        } else {
            dfs(nums, i + 1, sum);
            dfs(nums, i + 1, sum + nums[i]);
        }
    }


    public int dp(int[] nums) {
        int n = nums.length;

        int[][] dp = new int[n + 1][3];
        dp[0][0] = 0;
        dp[0][1] = Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] % 3 == 0) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]);
            } else if (nums[i - 1] % 3 == 1) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            } else if (nums[i - 1] % 3 == 2) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }
        return dp[n][0];
    }

    public int dp1(int[] nums) {
        int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int i = 0; i < nums.length; i++) {
            int mod = nums[i] % 3;
            int[] temp = new int[3];
            for (int j = 0; j < dp.length; j++) {
                temp[j] = Math.max(dp[j], dp[(3 - mod + j) % 3] + nums[i]);
            }
            dp = temp;
        }
        return dp[0];
    }

//  https://www.jianshu.com/p/dc9892479338

//    作者：andy-181
//    链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/solution/dpjie-fa-zhuang-tai-zhuan-yi-by-andy-181/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public static void main(String[] args) {
        MaxSumDivThree divThree = new MaxSumDivThree();
        int[] nums = {3, 6, 1, 8, 5};
        int max = 0;
//        max = divThree.math(nums);
//        System.out.println(max);
//        max = divThree.dfs(nums);
//        System.out.println(max);
        max = divThree.dp(nums);
        System.out.println(max);
    }

}